package Hash;

public class HashBuck {
    Node[] array = new Node[10];
    int usedSize;

    //插入操作
    public void put(int key, int val) {
        Node node = new Node(key, val);
        int index = key % array.length;
        Node cur = array[index];

        //遍历查看是否存在这个数——更新
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //没有这个数
        //头插法
        node.next = array[index];
        array[index] = node;
        usedSize++;

        if (loadFactor() >= 0.75) {
            resize();
        }
    }

    //扩容操作
    public void resize() {
        Node[] tmpArray = new Node[array.length * 2];

        //遍历，然后重新哈希
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                //标记当前节点的下一个节点
                Node curNext = cur.next;
                int index = cur.key % tmpArray.length;
                //头插
                cur.next = tmpArray[index];
                tmpArray[index] = cur;
                cur = curNext;
            }
        }
        array = tmpArray;
    }


    //查找
    public int get(int key) {
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    public double loadFactor() {
        return usedSize * 1.0 / array.length;
    }

    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.put(13, 5);
        hashBuck.put(23, 8);
        hashBuck.put(33, 7);
        hashBuck.put(93, 6);
        hashBuck.put(1, 5);
        hashBuck.put(9, 6);

        int x = hashBuck.get(9);
        System.out.println(x);

    }
}